Chapter 6 Flexible Shape Extraction: CHAPTER6.MCD

We'll use some operators from Chapter 3. If you want to write images out or to see them as pictures, you'll need to normalise them:

and we'll often need to clear them

From Chapter 4, we'll start using edge magnitude now, so we need the Sobel operator, and edge magnitude and direction

We'll need some of the (Fourier transform) operators from Chapter 2:

Feature Extraction & Image Processing,

M. S. Nixon and A. S. Aguado

Elsevier/ Butterworth Heinmann, 2nd Edition 2007

This worksheet is the companion to Chapter 6 and implements the snake and symmetry techniques described therein. The worksheet follows the text directly.

The main evolutionary technique is a snake, an active contour model. This evolves a set of points to a target shape. The evolution is a compromise between the snake's properties and some chosen image properties.

We'll need an initial contour. We'll use the function points to generate a set of no points arranged in a circle, radius rad, centre xc,yc.

and sometimes we'll want to threshold them

for all snake points,

set x co-ordinate of point

set y co-ordinate, then set

elasticity weighting for snake point

We'll need some noise

curvature weighting for snake point

edge weighting for snake point

each snake point is a vector of co-ordinates and the weighting coefficients

We'll need to check points are within an image

return the set of points

One of the snake's properties is by how much points are allowed to move. This is called the elastic energy. It is measured by the dist function which measures the distance between one point and the next.

We'll need to find the co-ordinates of a point with a known value (brightness)

We'll be plotting Fourier transforms as their logarithm (to see what's in them) using

We will need to measure the distance between an image point and a contour point. For this, we'll use the dist2 function

and we'll need to shift an image around by

The contour energy at a particular point is difference between the total distance between the points in the contour and the distance of that point from the currently selected contour point. The is the energy Econt

We will also need to measure the flexibility of the snake. This is the curvature energy Ecur which is measured by an approximation to a second order differential along the snake.

The edge data needs to be normalised so that it lies within the range 0 to 1 so that it is balanced with the snakes own forces. We'll normalise the edge image using edge_normalise

We'll normalise the curvature and elasticity energy local, within the 3x3 window. As with the previous function, we could use our usual normalise operator but this would sacrifice resolution. So we'll just normalise by the same equation, but into a range [0,1] using the operator balance

The Greedy function grdy which evolves the snake points is then:

analyse all snake point

doing the first one again at the end

initialise x,y co-ordinates of energy minimum

balance energy forces

initialise energy: first set elasticity

then add the curvature energy

and finally, the edge energy

analyse a 3*3 region around all snake points

if point is within the image

work out the energy at that point: elasticity + curvature + edge energy

if its a better minimum

store it!

return co-ordinates of the new minimum

return the new contour

Finally, we'll need the function draw_points to superimpose the contour onto an image so that we can see what's happening.

So let's read in the eye image again

find the edges

and normalise them.

Now let's define an initial contour

So our initial contour is a circle surrounding the eye. The contour aims to shrink to find the iris

Let's try one iteration of our Greedy algorithm

The right hand side has moved towards the eye; the left hand side has also moved in, but not by as much.

Let's try another iteration

The right hand side has nearly reached the eye, the bottom side has snagged on the strong contrast at the eyelid.

6

These illustrate that the snake converges to its target, but also shows some of the inherent difficulties. It's got stuck on the bottom, but is fine on the top Also, it can carry on, trying to find a better local miminum Try playing with the parameters (in the grdy function), the weighting factors affecting the compromise between the snake's properties and the image properties. Can you find an optimum set to find the iris? Since you'll doubtless have difficulty in convergence, try using the spade image to see what you can get (we'll be doing this in the next Chapter anyway).

We'll now move on to the Kass snake (the original formulation) which solves for all snake points in one iteration and uses a continuous formulation, as opposed to the (discrete) Greedy implementation. As a result of the formulation, all snake points are real as opposed to integer co-ordinates.

To address snake points modulo their number, we'll need a positive modulus function as

The snake's characteristic matrix is formulated according to the following functions:

and the characteristic matrix is then calculated by

we need to scale contour points by the time step delta by

then, contour evolution is controlled by

the contour operates on differential edge data which is given by

and we'll need to integerise contour points to plot them as

So let's detect the edges

normalise them

differentiate them again

starting contour

iteration 1

iteration 2

The last bit of this Chapter will be on skeletonisation. It's an alternative paradigm for finding shapes to find their medial axis. Essentially, techniques are either too prone to noise or too slow, to be of effective use. They are good, but need improvement in many respects.

We'll start with the distance transform: this labels points in an image with the number of iterations needed to erode from the perimeter to get to that point.

Then you work it out

Let's define a unit rectangle

and then evaluate the distance transform.

Ok, you get a transform. You can use non-maximum supression to obtain the skeleton. Let's just see what happens with a single noise spot.

Bit of a doh, really. Ok, morphology can fill the holes (or you could simply zap single black points), but it does certainly reflect susceptibility to noise.

Finally, we'll look at an operator which detects symmetry. Essentially, the generalised symmetry operator accumulates evidence of points which have symettrical properties.

We'll need an arctangent operator which returns in a larger interval, -2p to 2p, as opposed to Mathcad's operator.

Unfortunately, Mathcad's atan2 operator is very flakey indeed. So we approximate.

The distance between two points with co-ordinates (a,b) and (c,d) is:

The distance weight function acting from these two points is given by:

Th standard deviation s controls the influence: large values of s imply that far away points can contribute to the symmetry map as well as close ones whereas small values imply that only close points can contribute. To explain this graphically, let's define a function Di as

and a range of values for the variable is

so for a small value of s

and a large value

We also need a phase weighting function which depends on the direction of two points (again with co-ordinate (a,b) and (c,d) and evaluates the direction as

The phase weighting function is then

Let's have a look at this function for angles in the range

in the first component, the weighting is minimum for points with parallel tangents normal to the line joining the points

its second component maximised for opposite tangents

Now we need a function to plot a value at the mid-points of two points

Finally, the operator which delivers the symettry map is:

Let's define a rectangle

and get the edges

We'll evaluate the symmetry maps for large scale and small scale symmetry (using a large value of s and a small value, respectively), on a square

So high symmetry detects the central axis and low symmetry detects the corners. Intuitively correct!

That looks good: the symmetry of the spade is concentrated around the centre, the low value gives the corners.

So we can now find shapes in an image. Again, there's a variety of techniques, all of which collocate border pixels to find a shape. As with previous Chapters, try using different values for any controlling parameters to judge their effect. Try different images to see how the techniques perform.

Later, we'll look at some more sophisticated techniques for feature extraction. Before then though, we need to know how to describe shapes for purposes of recognition and analysis. Say we've used the GHT, or template matching, we then want to be able to analyse the match between the shape we've found, and the shape we're looking for. This requires us to be able to describe that shape. This is the subject of the following chapter: Chapter 6 Feature Description.